1. 题目描述（简单难度）

[warning] 429. N 叉树的层序遍历

2. 解法一： 广度优先搜索(BFS)

使用队列进行广度优先搜索

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        if(null == root){
            return new ArrayList<>();
        }
        List<List<Integer>> resp = new ArrayList<>();
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            List<Integer> ans = new ArrayList<>();
            int size = deque.size();
            for(int i=0;i<size;i++){
                Node poll = deque.poll();
                ans.add(poll.val);
                List<Node> children = poll.children;
                for(Node node : children){
                    deque.offer(node);
                }
            }
            resp.add(ans);
        }
        return resp;
    }
}

循环可以使用addAll进行优化

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        if(null == root){
            return new ArrayList<>();
        }
        List<List<Integer>> resp = new ArrayList<>();
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            List<Integer> ans = new ArrayList<>();
            int size = deque.size();
            for(int i=0;i<size;i++){
                Node poll = deque.poll();
                ans.add(poll.val);
                deque.addAll(poll.children);
            }
            resp.add(ans);
        }
        return resp;
    }
}

3. 解法二： 深度优先搜索(DFS)

class Solution {

    List<List<Integer>> resp = new ArrayList<>();
    public List<List<Integer>> levelOrder(Node root) {
      if(root == null){
          return new ArrayList<>();
      }
      traverseNode(root,0);
      return resp;
    }

    public void traverseNode(Node root,int level){
        if(resp.size() <= level){
            resp.add(new ArrayList<>());
        }
        resp.get(level).add(root.val);
        for(Node node : root.children){
            traverseNode(node,level+1);
        }
    }
}